\documentclass[12pt,a4paper,oneside,final]{book}
\usepackage[utf8]{inputenc}
\usepackage[IL2]{fontenc}
\usepackage[czech]{babel}
%\usepackage{mathptmx}
\usepackage{longtable}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{amsfonts}



\theoremstyle{plain}
\newtheorem{veta}{Věta}[section]
\newtheorem{lemma}[veta]{Lemma}

\theoremstyle{definition}
\newtheorem{definice}[veta]{Definice}
\newtheorem{pozn}[veta]{Poznámka}


\begin{document}
\chapter*{Úvod}
V dnešní době moderní matematiky převládá snaha zkoumat problémy v co možná nejobecnější formě. Zvlášť obory, jako je algebra, kombinatorika, nebo teoretická informatika, jsou vystavěny na abstraktních pojmech a definicích a člověk potom jen těžko pozná, na jaké konkrétní problémy se daná teorie vztahuje, nebo jaké má aplikace. Tento problém se však netýká pouze přímého využití v praxi. Velice často se zjišťuje, že dva pojmy, které spolu nemají zdánlivě mnoho společného, dávají dohromady velice zajímavé a důležité výsledky, kterých by se jinak dosahovalo velice složitě. Jedním s těchto případů je využití relace dobré předuspořádání v teorii formálních jazyků. 

Jedním z hlavních problémů zkoumaných v teorii formální jazyků je otázka, za jakých podmínek je daný jazyk regulární. Regulární jazyk je definován jako množina popsaná nějakým regulárním výrazem, regulární gramatikou nebo konečným automatem. Spojitost těchto pojmů se vysvětluje v základních kurzech formálních jazyků. Ukazuje se tak výhoda, kterou je zkoumaní jednoho pojmu pomocí různých přístupů. Regulární jazyky mají mnoho zajimavých vlastností, jako je například uzavřenost na množinové booleovské operace, zřetězení, Kleeneho hvězdičku nebo homomorfismy. Co se však může zdát jako složitý problém, má mnohdy jednoduché řešení při využití jiného přístupu. 

Jedním ze základních výsledků formálních jazyků je Nerodova věta, která popisuje regulární jazyky jako množiny vyplněné třídami nějaké kongruence (monotónní ekvivalence) konečného indexu. Tento výsledek je vlastě snaha o algebraický popis faktu, že je daný jazyk rozpoznáván konečným automatem. Třídy ekvivalentních slov totiž odpovídají stavům daného automatu. Tento výsledek se dá ovšem zobecnit a místo relace ekvivalence se uvažuje obecnější relace předuspořádání. Ukazuje se, že v případě předuspořádání se podmínka na konečnost dá nahradit slabší podmínkou, aby předuspořádání bylo dobré. 

Dalším z formalismů studovaných teorií formálních jazyků jsou přepisovací systémy, anglicky někdy označované jako semi-Thue systems. Ty indukují na množině všech slov předuspořádání a nabízí proto otázka, za jakých podmínek je toto předuspořádání dobré. V takových případech jsou jazyky uzavřené na tento přepisovací systém regulární. Ukážeme si několik tříd přepisovacích systémů, které tuto podmínku splňují.

pokračování




\chapter{Připomenutí pojmů}

\begin{definice}
\label{monotonie}
  Nechť $\Sigma$ je abeceda a $\rho$ binární relace na množině $\Sigma^*$.
  Řekneme, že $\rho$ je \emph{monotónní}, pokud pro každé $x_1, x_2, y_1, y_2 \in \Sigma^*$ platí:
  \[x_1 \: \rho \: y_1, \: x_2 \: \rho \: y_2   \Rightarrow x_1 x_2 \: \rho \: y_1 y_2       \]
  Řekneme, že $\rho$ je zprava (zleva) \emph{monotónní}, pokud pro každé $x_1, x_2, y \in \Sigma^*$ platí:
   \[x_1 \: \rho \: x_2,  \Rightarrow x_1 y \: \rho \: x_2 y \;\;\; (y x_1 \: \rho \: y x_2)      \]
  Relace ekvivalence $\sim$ na množine $\Sigma^*$, která je (zprava) monotónní se nazývá (pravá) \emph{kongruence}.
\end{definice}   

Následující věta jinak známá jako Nerodova dává základní algebraickou charakterizaci regulárních jazyků.

\begin{veta}
\label{nerode}
  Nechť $L\subseteq\Sigma^*$. Potom $L$ je regulární právě tehdy, když je sjednocením některých tříd pravé kongruence na $\Sigma^*$ konečného indexu.
\end{veta}

  Abychom na základě předchozího tvrzení mohli o některém jazyku $L$ tvrdit, že je regulární,
  stačí nám nalézt vhodnou kongruenci konečného indexu a ukázat, že daný jazyk je vyplněn nekterými
  třídami ekvivalence. Pokud bychom však chtěli tvrdit opak, tedy že $L$ není regulární, stáli bychom před nelehkým úkolem.
  Museli bychom ukázat, že žádná kongruence požadovaných vlastností neexistuje.  
  Tento problém řeší silnější tvrzení, tzv. Myhill-Nerodova věta, která se opírá o pojem kontextu.

\begin{definice}
\label{kontext}
  Nechť $L\subseteq\Sigma^*$ je jazyk (ne nutně regulární). Potom pro libovolné $x\in\Sigma^*$ definujme množinu \emph{kontextů} prvku $x$ v jazyce $L$ takto:
  \[C_L(x)=\{(y,z)\mid y,z \in \Sigma^*, yxz \in L\}.\]
Dále definujme pravý a levý kontext (prefix, suffix) následovně:
  \[C_L^r(x)=\{y \in \Sigma^*, xy \in L\},\]
  \[C_L^l(x)=\{y \in \Sigma^*, yx \in L\}.\]
Na základě pravého kontextu můžeme nyní zadefinovat relaci $\sim_L^r$ :
  \[x\sim_L^r y  \Longleftrightarrow C_L^r(x) = C_L^r(y).\]
\end{definice}  

Relaci $\sim_L^r$ se říká \emph{pravá syntaktická ekvivalence} a je zřejmé, že jde o pravou kongruenci.
Relace $\sim_L^r$ má tu vlastnost, že pro libovolný jazyk $L$ platí, že je sjednocením některých
tříd $\Sigma^*/_{\sim_L^r}$. 

\begin{lemma}
Nechť $L\subseteq\Sigma^*$. Potom $L$ je sjednocením některých tříd rozkladu  $\Sigma^*/_{\sim_L^r}$.
\end{lemma}

\begin{proof}
Chceme dokázat, že pro libovolné $x \in \Sigma^*$ patří třída $[x]_{\sim_L^r}$ buď celá do $L$, nebo s ním má prázdný průnik. Nechť tedy $y$ je libovolné slovo takové, že $x\sim_L^r y$. Potom podle definice platí  $C_L^r(x) = C_L^r(y)$, neboli $xz \in L \Longleftrightarrow yz \in L$. Zvolme tedy $z=\epsilon$ a dostaneme $x \in L \Longleftrightarrow y \in L$.
\end{proof}

Další zajímavou vlastností je, že každá pravá kongruence, pro kterou platí, že je jazyk
$L$ sjednocením jejích tříd ekvivalence, je zjemněním relace $\sim_L^r$. Je tedy ze všech takových kongruencí největší.
Tato vlastnost je formálně shrnuta v následujícím lemmatu. 

\begin{lemma}
  Nechť $L\subseteq\Sigma^*$ a $\sim$ je libovolná pravá kongruence na množině $\Sigma^*$ taková, že $L$ je sjednocením některých tříd rozkladu. Potom platí, že $\sim ~\subseteq ~ \sim_L^r$. 
\end{lemma}
\begin{proof}
Dokážeme, že pro libovolná slova $x, y$ taková, že platí $x \sim y$ , platí také $x \sim_L^r y$. Relace $\sim$ je pravá kongruence, a proto platí  $xz \sim yz$ pro libovolné $z \in \Sigma^*$.
Protože $L$ je sjednocením některých tříd ekvivalence  $\sim$, platí $xz \in L \Longleftrightarrow yz \in L$. Tento vztah platí pro libovolné $z$, z toho vyplývá rovnost $C_L^r(x)=C_L^r(y)$ a tedy $x \sim_L^r y$.

\end{proof}

Z Nerodovy věty a předchozího tvrzení už přímo plyne Myhill-Nerodova věta.
 
\begin{veta}
\label{Myhill-Nerode}
  Nechť $L\subseteq\Sigma^*$. Potom jsou následující tvrzení ekvivalentní:
  \begin{enumerate}
    \item[(i)] L je regulární jazyk.
    \item[(ii)] Relace $\sim_L^r$ má konečný index.
  \end{enumerate}
\end{veta} 



Myhill-Nerodova věta je tedy podstatně silnější. Říká nám přesně na kterou
z pravých kongruencí se máme zaměřit. Navíc v případě, že má tato kongruence nekonečný 
index, nemůže být zkoumaný jazyk regulární. 

Předchozí věta nám dává nutnou i postačující
podmínku regularity jazyka a tedy úplnou charakterizaci. Zjistit, zda je
konkrétní jazyk regulární lze však více způsoby. Například sestrojením konečného automatu rozpoznávajícího daný jazyk, nebo pomocí
uzávěrových vlastností. My se zaměříme na některá zobecnění Myhill-Nerodovy věty.

Pro aplikaci Nerodovy věty bylo třeba nalézt pravou kongruenci (monotónní ekvivalenci) konečného indexu. Místo ekvivalence však můžeme uvažovat
obecnější relaci, a to předuspořádání.  

\begin{definice}
  Binární relace $\leq$ na množině $S$ se nazývá \emph{předuspořádání}, právě když je reflexivní a tranzitivní.

  Nechť $X \subseteq S$. Potom říkáme, že množina $X$ je \emph{nahoru uzavřená} vzhledem k $\leq$ ,
  pokud pro libovolné prvky $x \in X$ a $s \in S$ platí:
  \[x \leq s \Longrightarrow s \in X.\]
  Dále budeme nahoru uzavřené množiny nazývat pouze \emph{uzavřené}. 
  
  Relace ekvivalence $\sim$ na $S$ definovaná vztahem
    \[x \: \sim \: y  \Longleftrightarrow x  \: \leq \: y \; \text{a zároveň} \; y  \: \leq \: x      \]
  se nazývá \emph{jádro předuspořádání $\leq$}.   
\end{definice}

Věta \ref{Myhill-Nerode} se nyní přeformuluje do následujícího znění.

\begin{veta}
\label{Myhill-preorder}
  Nechť $L\subseteq\Sigma^*$. Potom $L$ je regulární právě tehdy, když je uzavřený vzhledem k nějakému 
  monotónnímu předuspořánaní množiny $\Sigma^*$, jehož jádro má konečný index.
\end{veta}

Jak je vidět, přechodem k předuspořádání jsme se nikam významně neposunuli. Věta se totiž stále odvolává na ekvivalenci konečného indexu.
Platí totiž, že je-li jazyk $L$ uzavřený vzhledem k monotónnímu předuspořádání $\leq$, jehož jádro má konečný index,
pak je $L$ sjednocením některých tříd jádra $\leq$. Věta \ref{Myhill-preorder} je tedy pouze přeformulovaná věta  \ref{Myhill-Nerode}.
Tento postup byl původně použit z jiných důvodů, monónní předuspořádání dávájí totiž jenmější klasifikaci regulárních jazyků.
Zajimavé je však zamyšlení, jestli nelze rozpoznávat regulární jazyky i předuspořádáními nekonečných indexů.
Hledaným zobecněním jsou dobrá předuspořádání, kterým se bude věnovat následující kapitola.

\chapter{Dobrá předuspořádání}


V této kapitole se zaměříme na pojem \emph{dobré předuspořádání}. 
Nejprve zadefinujeme potřebné pojmy a následně si  ukážeme vztah 
dobrých předuspořádí s regulárními jazyky. Ve zbytku kapitoly si popíšeme několik způsobů jak dokázat, že předuspořádání je dobré.


Dobré předuspořádání je reflexivní a tranzitivní relace (předuspořádání),
pro kterou platí, že každá podmnožina obsahuje alespoň jeden minimální prvek a nejvýše 
konečně mnoho takových, které nejsou vzájemně ekvivalentní. 

Jde o zobecnění pojmu \emph{dobrého uspořádání} 
a tento popis se definici dobrého uspořádání nejvíce blíží. Existuje však více zbůsobů jak definovat dobré předuspořádání, z nichž několik uvedeme
 v následující definici. 
 
\begin{definice} 
\label{wqo}
 Předuspořádání $\leq$ na množině $S$ je \emph{dobré předuspořádání} právě tehdy, když platí jedno z následujících:

\begin{enumerate}
  \item[(i)] Každá podmnožina $X \subseteq  S$ obsahuje konečnou podmnožinu $Y\subseteq X$ takovou, 
  že
  \[ \forall x \in X \  \exists y \in Y : y \le x.\]
  \item[(ii)] V libovolné posloupnosti $\{ x_i \}_{i=1}^\infty $ existují $i,j \in \mathbb{N}, i < j$ taková,
   že platí $x_i \leq x_j.$ 
  \item[(iii)] Libovolná nekonečná posloupnost prvků z $S$ obsahuje nekonečnou rostoucí podposloupnost.
  \item[(iv)] Množina $S$ neobsahuje ostře klesající nekonečnou posloupnost ani nekonečnou posloupnost vzájemně neporovnatelných prvků.
  \item[(v)] Libovolná posloupnost uzavřených podmnožin $S$, která je ostře rostoucí vzhledem k inkluzi, je konečná.
\end{enumerate}
\end{definice}

Lze jednoduše ověřit, že všech pět definic je ekvivalentních.
První z podmínek se nazývá \emph{vlastnost konečné báze}. Každá uzavřená množina $X$ totiž obsahuje konečnou podmnožinu, jejímž uzávěrem je 
právě množina $X$, která je tak konečně generovaná.Při rozpoznávání jazyků monotónními předuspořádáními nám k regularitě místo konečného indexu stačí vlastnost konečné báze, jak vyplyne z důkazu následující věty.
Důkaz samotný je převzat z ??.


\begin{veta}
\label{genMyh}
Nechť $L\subseteq\Sigma^*$. Potom $L$ je regulární právě tehdy, když je uzavřený vzhledem k nějakému 
monotónnímu dobrému předuspořánaní množiny $\Sigma^*$.
\end{veta}

\begin{proof}


Je jednoduché si uvědomit, že každé předuspořádání konečného indexu je dobré. Stačí nám tedy ukázat, že podmnožiny množiny $\Sigma^*$ uzavřené
vzhledem k monotónnímu dobrému předuspořádání jsou regulární. Důkaz provedeme sporem. Předpokládejme tedy, že máme monotónní dobré předuspořádání $\leq$ na množině
$\Sigma^*$ a množinu $L$ uzavřenou vzhledem k $\leq$, která není regulární. Z věty \ref{Myhill-Nerode} plyne, že relace $\sim_L$ má nekonečný index,
můžeme proto sestrojit nekonečnou posloupnost vzájemně neekvivalentních slov $\{x_i\}_{i=1}^\infty$. Podle definice \ref{wqo} můžeme z posloupnosti $\{x_i\}_{i=1}^\infty$
vybrat rostoucí podposloupnost vzhledem k $\leq$. Můžeme tedy předpokládat, že už samotná posloupnost $\{x_i\}_{i=1}^\infty$ byla vybrána jako rostoucí.
Z monotónie dostáváme, že pro libovolné $y \in \Sigma^*$ a $i < j $ platí $x_i y \leq x_j y$ a z uzavřenosti množiny $X$ plyne, že 
$x_i y \in L \Longrightarrow x_j y \in L $. Proto platí, že posloupnost pravých kontextů $\{C_L^r(x_i)\}_{i=1}^\infty$ je rostoucí vzhledem k inkluzi, a to dokonce ostře, 
neboť slova $x_i$ nejsou vzájemně ekvivalentní. Dále pro libovoná slova $y_1, y_2 \in \Sigma^*$ taková, že $y_1 \leq y_2$, platí $x_i y_1 \in L \Longrightarrow x_i y_2 \in L $.
Jsou tedy množiny $C_L^r(x_i)$  rovněž uzavřené vzhledem k  $\leq$. Posloupnost $\{C_L^r(x_i)\}_{i=1}^\infty$ je tedy nekonečná posloupnost uzavřených množin
ostře rostoucí vzhledem k inkluzi. Dostáváme spor, neboť podle definice \ref{wqo} části (v) takováto posloupnost není možná. Množina $L$ 
tedy musí být regulární.
 \end{proof}

V předchozím tvrzení jsme dostali zobecnění Nerodovy věty tím, že místo pravé kongruence jsme použili monotónní předuspořádání. V důkazu jsme využili monónnost z prava i zleva,
v případě kongruence nám však stačila pouze monotonie z prava. Jak se ukáže na příkladu, uzavřenost vzhledem k dobrému předuspořádání monotónnímu z prava k regularitě vést nemusít.

Příklad! ($\{ a^n b^m, kde \; n\leq m \}$)

Jednostranná monotonie tedy k regularitě nevede, věta \ref{genMyh} se přesto dá zobecnit. Stačí nalézt dvě dobrá předuspořádání $\leq_1 , \leq_2$, vzhledem k nimž bude jazyk $L$ uzavřený, přičemž $\leq_1$ je monotónní zprava
a $\leq_2$ zleva. 

\begin{veta}
\label{genMyh2}
Nechť $L\subseteq\Sigma^*$.  Potom $L$ je regulární právě tehdy, když je uzavřený vzhledem k nějakému 
 dobrému předuspořánaní  $\leq_1$ monotónnímu zprava a  dobrému předuspořánaní  $\leq_2$ monotónnímu zleva.

\end{veta}

K důkazu věty budeme potřebovat několik pojmů. Podobně jako jsme v definici \ref{kontext} definovali na základě kontextu syntaktickou kongruenci, si zadefinujeme \emph{syntaktické monotónní předuspořádání}.

\begin{definice}
Pro $L \subseteq\Sigma^* $ a prvky $x,y \in \Sigma^*$ definujeme relace:
  \[x\leq_L y  \Longleftrightarrow C_L(x) \subseteq C_L(y).\]
  \[x\leq_L^r y  \Longleftrightarrow C_L^r(x) \subseteq C_L^r(y).\]
  \[x\leq_L^l y  \Longleftrightarrow C_L^l(x) \subseteq C_L^l(y).\]
\end{definice}
Podobně jako v případě syntaktické kongruence se snadno ukáže, že syntaktické monotónní předuspořádání (resp. pravé/lévé) je největší monotónní předuspořádání, vzhledem k němuž je jazyk $L$ uzavřený.

\begin{lemma}
\label{monwqo}
 Nechť $L\subseteq\Sigma^*$ a $\leq$ je libovolné pravé (resp. levé) monotónní  předuspořádání na $\Sigma^*$, vzhledem ke kterému je jazyk $L$ uzavřený.  Potom platí, že $\leq \;\subseteq\; \leq_L^r$ (resp. $\leq \;\subseteq\; \leq_L^l$ ). 
\end{lemma}



\begin{proof}
Budeme dokazovat případ pro pravé monotńní předuspořádání.
Nechť  $x, y \in \Sigma^*$ jsou libovolná slova taková, že platí $x \leq y$. Z monotónnie $\leq$ plyne, že $xz \leq yz$ pro libovolné $z \in \Sigma^*$. 
Z uzavřenosti jazyka $L$ vzhledem k $\leq$ potom vyplývá, že $xz \in L \Longrightarrow yz \in L$ a tedy $ C_L^r(x) \subseteq C_L^r(y)$.

\end{proof}

Poslední vlastnost, kterou v důkazu věty \ref{genMyh2} využijeme, je, že se stačí zaměřit právě na předuspořádání $\leq_L^r$ a $\leq_L^l$. Najdeme-li totiž nějaká předuspořádání $\leq_1 , \leq_2$, která splňují podmínky věty \ref{genMyh2}, pak mají tuto vlastnost i $\leq_L^r$, $\leq_L^l$.

\begin{lemma}
\label{subwqo}
Nechť  $\leq_1$ je dobré předuspořádání a  $\leq_2$ je předuspořádání takové, že platí   $\leq_1\subseteq  \leq_2$. Potom je předuspořádání $\leq_2$ dobré.
\end{lemma}
\begin{proof}
K důkazu využijeme definici \ref{wqo}(ii). Pro  $\leq_1$ platí, že v libovolné posloupnosti $\{ x_i \}_{i=1}^\infty $ existují $i,j \in \mathbb{N}, i < j$ taková,
   že $x_i \leq_1 x_j$, tedy i   $x_i \leq_2 x_j$. Předuspořádání  $\leq_2$ je proto také dobré.
\end{proof}

\begin{proof}[Důkaz věty \ref{genMyh2}]
Je-li jazyk $L$ regulární, pak podle věty \ref{genMyh} víme, že je uzavřený vzhledem k dobrému předuspořádání, které je monotónní zprava i zleva. Opačnou implikaci budeme dokazovat sporem.
Nechť tedy $L$ není regulární. Potom podle věty \ref{Myhill-Nerode} má relace $\sim_L^r$ nekonečný index a existuje proto nekonečná posloupnost vzájemně neekvivalentních slov $\{x_i\}_{i=1}^\infty$. Podle předpokladu existují dobrá předuspořádání 
$\leq_1$ resp. $\leq_2$ monotónní zprava resp. zleva, vzhledem k nimž je $L$ uzavřený. Podle lemmat \ref{monwqo} a \ref{subwqo} mají tuto vlastnost také předuspořádání $\leq_L^r$, $\leq_L^l$. Z definice \ref{wqo}(ii) můžeme z posloupnosti $\{x_i\}_{i=1}^\infty$ vybrat podposloupnost $\{y_i\}_{i=1}^\infty$, která bude rostoucí vzhledem k předuspořádání $\leq_L^r$ a to dokonce ostře, neboť jsou $y_i$ vzájemně neekvivalentní v relaci $\sim_L^r$. Platí tedy, že 
$C_L^r(y_i) \subset C_L^r(y_{i+1})$ a posloupnost $\{C_L^r(y_i)\}_{i=1}^\infty$ je tedy ostře rostoucí vzhledem k inkluzi. Je zřejmé, že platí vztah $x\in C_L^r(y) \Longleftrightarrow y\in C_L^l(x) $. Z toho pro libovolná $z_1 \leq_L^l z_2$ plyne, že $z_1 \in C_L^r(y_i) \Longrightarrow y_i \in C_L^l(z_1) \subseteq C_L^l(z_2) \Longrightarrow z_2\in C_L^r(y_i)$.  Posloupnost $\{C_L^r(y_i)\}_{i=1}^\infty$ je pak posloupností uzavřených množin vzhledem k předuspořádání  $\leq_L^l$, která je ostře rostoucí vzhledem k inkluzi. To je ovšem spor s předpokladem, že předuspořádání  $\leq_L^l$ je dobré.
\end{proof}

\begin{veta}
Nechť $\leq$ je rozhodnutelné monotónní předuspořádání množiny $\Sigma^*$, pro které platí $u \leq v \Longrightarrow |u| \leq |v|$. Potom jsou následující podmínky ekvivalentní:

\begin{enumerate}
  \item[(i)]Všechny uzavřené jazyky vzhledem k $\leq$ jsou regulární.
  \item[(ii)]Všechny uzavřené jazyky vzhledem k $\leq$ jsou rekurzivní.
  \item[(iii)] $\leq$ je dobré předuspořádání.
\end{enumerate}
\end{veta}

\begin{lemma}
\label{soucinwqo}
Nechť $X$ je pologrupa předuspořádaná monotónní relací $\leq$ a $T_1, T_2 \subseteq X$. Pokud $\leq$ je dobré předuspořádání množin $T_1, T_2$, potom je dobré i na množině $T_1\cdot T_2$. 

\end{lemma}

Užitečným nástrojem pro dokázání, že dané předuspořádání je dobré, poskytuje věta, kterou poprvé dokázal Nash-Williams. K jejímu formulování potřebujeme definovat následující pojem.

\begin{definice}
Nechť $X$ je množina s předuspořádáním $\leq$ a $(x_i)_{i=1}^\infty$ je nekonečná posloupnost prvků množiny $X$. Posloupnost   $(x_i)_{i=1}^\infty$ nazveme \emph{špatnou}, právě když platí
\[  \forall i,j \in \mathbb{N} : i < j  \Longrightarrow x_i \not \leq x_j.\]
\end{definice}

Název \emph{špatná posloupnost} odpovídá tomu, že jsou to práve tyto posloupnosti, které nesmí obsahovat dobře předuspořádaná množina (\ref{wqo}(ii)).

\begin{definice}
Nechť $\leq$ je předuspořádání na množině $X$. Potom předuspořádání $\leq$ nazveme \emph{fundované}, právě když neexistuje nekočná posloupnost  $(x_i)_{i=1}^\infty, x_i \in X$, pro kterou platí $x_{i}>x_{i+1}, i \in \mathbb{N}$.
\end{definice}

Uveďme, že každé dobré předuspořádání je fundované, jak vyplývá z definice \ref{wqo}(iv).

Pro potřeby následující věty je nutné definovat lexikografické předuspořádání na nekonečných posloupnostech. Nechť $X$ je množina předuspořádaná relací $\leq$ a $\sim$ je její jádro. Definujme množinu nekonečných posloupností jako $X^{\omega}$. Potom předuspořádání $\leq$ indukuje předuspořádání na množině $X^{\omega}$ následujícím vztahem:
\[ (x_i)_{i=1}^\infty \leq  (y_i)_{i=1}^\infty \Longleftrightarrow \forall i \in \mathbb{N} : x_i \sim y_i \text{ nebo}\]
\[ \exists n : x_n \leq y_n \wedge \forall i<n : x_i \sim y_i     .\]

\begin{veta}

Nechť $\preceq$ je fundované předuspořádání na množině $X$. Nechť dále $\leq$ je předuspořádání na množině $X$, které není dobré. Potom existuje špatná posloupnost $(x_i)_{i=1}^\infty, x_i \in X$ vzhledem k předuspořádání $\leq$, která je minimální vzhledem k $\preceq$.

\end{veta}


\chapter{Přepisovací systémy}

V této kapitole si vysvětlíme pojem přepisovací systém a aplikuje dosavadní poznatky o vztahu regulárních jazyků s dobrými předuspořádáními. Přepisovací systémy mají stejnou vyjadřovací sílu jako Turingovy stroje. Nás bude zajímat, za jakých okolností jsou jazyky uzavřené vzhledem k danému přepisovacímu systému regulární. Ukáže se, že přepisovací systémy generují regulární jazyky právě když indukují dobré předuspořádání na slovech nad danou abecedou. Dále se zaměříme na  konkrétní třídy přepisovacích systémů a ukážeme, že indukují dobrá předuspořádání.

Přepisovací systémy

\begin{definice}
\emph{Přepisovací systém} je dvojice $(\Sigma, R)$, kde $\Sigma$ je abeceda a $R \subseteq \Sigma^* \times \Sigma^*$ je konečná množina dvojic slov, které se nazývají \emph{přepisovací pravidla}. Pravidlo $(u, v) \in R$ se také zapisuje $u \rightarrow v$, čímž se myslí, že slovo $u$ se přepíše na $v$. Relace $R$ se dá přirozeně rozšířít na další slova nad abecedou $\Sigma$ na relaci $\Rightarrow_R$  podle pravidla:
\[ x \Rightarrow_R y \Longleftrightarrow x=x_1 u x_2  \; \text{ a }  \; y = x_1 v x_2,  \: \text{kde}  \: x_1, x_2 \in \Sigma^*  \: \text{ a }  \: u \rightarrow v        .\]
Konečně reflexivní a tranzitivní uzávěr relace $\Rightarrow_R$ se značí $\Rightarrow_R^*$ a nazývá se \emph{relace odvození}.

\end{definice}

Pro libovolný přepisovací systém $(\Sigma, R)$ je tedy relace odvození $\Rightarrow_R^*$ předuspořádání na množině $\Sigma^*$. Vzhledem k definici relace $\Rightarrow_R^*$ je zřejmé, že je monotónní. Následuje základní tvrzení této kapitoly, které přímo vyplývá z věty \ref{genMyh}.

\begin{veta}
\label{Thue}
Nechť $(\Sigma, R)$ je přepisovací systém a $L$ je jazyk nad abecedou $\Sigma$ uzavřený vzhledem k relaci $\Rightarrow_R^*$. Potom $L$ je regulární, pokud relace $\Rightarrow_R^*$ je dobré předuspořádání. 
\end{veta}

Ve zbytku kapitoly se budeme zaobírat konkrétními  třídami přepisovacích systémů. 

\section{Unitární přepisovací systémy}
Jako první se zaměříme na unitární přepisovací systémy.

\begin{definice}
Nechť $\Sigma$ je konečná abeceda. Přepisovací systém $(\Sigma, R)$ nazveme \emph{unitární}, pokud množina jeho pravidel je ve tvaru 
\[R=\{\epsilon \rightarrow w | w\in I\},\]
kde $I \subseteq \Sigma^*$ je konečná množina slov. V tom případě je přepisovací systém jasně určen množinou $I$, budeme proto jím indukovanou relaci odvození značit $\Rightarrow_I^*$.
\end{definice}
Přepisování podle pravidel unitárního systému tedy znamená vkládání řetězců z množiny $I$. Je tedy zřejmé, že unitární přepisovací systémy generují bezkontextové jazyky. V našem zájmu bude zjistit, za jakých podmínek jsou jazyky uzavřené na relaci odvození regulární, tedy kdy je $\Rightarrow_I^* $ dobré předuspořádání. Jak se ukáže, musí mít množina $I$ vlastnost nevyhnutelnosti.

\begin{definice}
Nechť $I \subseteq \Sigma^* $. Potom množina $I$ je \emph{nevyhnutelná} (nad abecedou $\Sigma$), pokud existuje přirozené číslo $k_0$ takové, že libovolné slovo $u \in \Sigma^* $, pro které platí $|u|>k_0$, je ve tvaru $u = u_1wu_2$ pro $w \in I$ a $u_1, u_2 \in \Sigma^*$. Nejmenší $k_0$ s touto vlastností nazveme \emph{mez nevyhnutelnosti}.
\end{definice}

Nevyhnutelnost tedy znamená, že libovolné slovo delší než nějaká mez musí jako podřetězec obsahovat nějaké slovo z množiny $I$. Následující tvrzení dává nutnou i postačující podmínku k tomu, aby unitární přepisovací systém indukoval dobré předuspořádání.

\begin{veta}
\label{unitar}
Nechť $(\Sigma, R)$ je unitární přepisovací systém spolu s množinou $I$. Potom relace odvození $\Rightarrow_I^*$ je dobré předuspořádání právě tehdy, když je množina $I$ nevyhnutelná.
\end{veta}

K důkazu předchozí vety bude třeba nekolik pomocných tvrzení, jejihž důkazy lze najít například v ??.
Nejprve zadefinujeme posloupnost množin $(I_i)_{i=0}^\infty$ následovně:
\[I_0 = I^*, \: I_{n+1}=( \bigcup_{a_1, ... ,a_k \in \Sigma, a_1 \cdots  a_k \in I}I_n a_1 I_n a_2 \cdots  a_{k-1}I_n a_k i_n)^*\]

\

\begin{lemma}
\label{unitar1}
Pro libovolné $n\leq0$ je relace odvození $\Rightarrow_I^*$ dobré předuspořádání množiny $I_n$.
\end{lemma}
***
\begin{lemma}
\label{unitar2}
Pro libovolné $n\leq0$ platí:
\begin{enumerate}
  \item[(i)]Pokud $uv \in I_n \text{ a } w\in I, \text{ pak } uwv\in I_{n+1},$
  \item[(ii)]Pokud $uv \in I_n, |u|\leq |v| \text{ a } w\in I, \text{ pak } uwv\in I_{n+1},$
\end{enumerate}
\end{lemma}

Dále definujme pro libovolné $n\leq0$:
\[R(I_n)= \bigcup_{a_1, ... ,a_k \in \Sigma,k\leq n}I_n a_1 I_n a_2 \cdots  a_{k-1}I_n a_k I_n.\]

\begin{lemma}
\label{unitar3}
Nechť I je konečná nevyhnutelná podmnožina množiny $\Sigma^*$ a $k_0$ je mez nevyhnutelnosti $I$. Potom platí, že $\Sigma^* = R(I_k)$.
\end{lemma}

\begin{proof}[Důkaz v2ty \ref{unitar}]
Nevyhnutelnost množiny $I$ je zřejmě nutná podmínka. Aby byla relace $\Rightarrow_I^*$ dobré předuspořádání, nesmí podle definice \ref{wqo}(iv) existovat nekonečná posloupnost neporovnatelných prvků.  Platí-li však $u \Rightarrow_I^* w$, musí slovo $w$ obsahovat podslovo z  množiny $I$. Pokud tedy množina $I$ není nevyhnutelná, existuje nekonečná posloupnost slov neobsahujícíh podslova z množiny $I$ a jsou proto vzájemně neporovnatelná.

Nechť nyní $k_0$ je mez nevyhnutelnosti množiny $I$. Potom z lemmatu \ref{unitar3} vyplývá
\[ \Sigma^*= \bigcup_{a_1, ... ,a_k \in \Sigma,k\leq k_0}I_{k_0} a_1 I_{k_0} a_2 \cdots  a_{k-1}I_{k_0} a_k I_{k_0}. \]
Podle lemmatu \ref{unitar1} je $\Rightarrow_I^*$ dobré předuspořádání množiny $I_{k_0}$ a podle lammatu \ref{soucinwqo} také množiny $\Sigma^*$.

\end{proof}

\begin{pozn}
\label{nevyhnutelnost}
Podle věty \ref{unitar} umíme rozhodnout, zda daný unitární systém generuje regulární jazyky.To nastane v případě, že množina $I$ je nevyhnutelná. K tomu stačí ověřit, že množina slov, která neobsahují podslovo z množiny $I$, je konečná. Tuto množinu lze zapsat ve tvaru $\Sigma^* -\Sigma^*  I \Sigma^* $. Pro $I$ regulární jde o rozhodnutelny problém.
\end{pozn}

\section{OS schémata* }

V této časti se zaměříme na obecné bezkontextové přepisovací systémy. Konkrétně jsou to takové, ve kterých jsou všechna pravidla tvaru $a \rightarrow w$, kde $a \in \Sigma, w\in \Sigma^*$. 

\begin{veta}
Nechť $(\Sigma, R)$ je přepisovací systém, kde $R= \{a_i \rightarrow w_i | a_i \in \Sigma, w_i \in \Sigma^* , i=1, 2, ..., n\}$. Potom jsou následující podmínky ekvivalentní:

\begin{enumerate}
  \item[(i)] Relace odvození $\Rightarrow_R^*$ je dobré předuspořádání.
  \item[(ii)]$\{awa \: | a \in \Sigma, w\in \Sigma^*, a\Rightarrow_R^*awa\}$ je nevyhnutelná nad $\Sigma$.
  \item[(iii)]$\{aw \:| a \in \Sigma, w\in \Sigma^*, w \neq \epsilon, a\Rightarrow_R^*aw\}\: \cup \newline \{wa \:| a \in \Sigma, w\in \Sigma^*, w \neq \epsilon, a\Rightarrow_R^*wa\}$ je nevyhnutelná nad $\Sigma$.
\end{enumerate}
\end{veta}

Poznamenejme, že v tomto případě nejdou podmínky věty efektivně rozhodnout. Argument z poznámky \ref{nevyhnutelnost} nelze použít, neboť tyto množiny nejsou regulární.


V na´sledujı´cı´ kapitole si uvedeme zobecneˇnı´ Eilenbergovy korespondence. Klasicka´ Eilenbergova
korespondence rˇı´ka´, zˇe trˇı´dy regula´rnı´ch jazyku°, ktere´ lze popsat pomocı´ pseudovariet
pologrup, jsou pra´veˇ variety jazyku°. V nasˇı´ pra´ci vsˇak budeme pracovat s modifikovanou
Eilenbergovou korespondencı´, ktera´ da´va´ do vztahu C -variety jazyku° a C -
pseudovariety homomorfismu°. Toto zobecneˇnı´ bylo zavedeno Howardem Straubingem
v [21]. Jeho prˇı´nos je v tom, zˇe oproti klasicke´ Eilenbergoveˇ korespondenci umozˇnˇuje charakterizovat
trˇı´dy jazyku°, ktere´ nejsou uzavrˇene´ na vzory ve vsˇech homomorfismech. Nynı´
totizˇ mu°zˇeme zkoumat uzavrˇenost teˇchto trˇı´d na vzory jen v neˇktery´ch homomorfismech,
naprˇ. de´lku zachova´vajı´cı´ch, de´lku na´sobı´cı´ch a podobneˇ. Podkladem pro tuto kapitolu
byly prˇeva´zˇneˇ texty [6], [21] a [24].
2.1 Za´kladnı´ definice
Uvazˇme trˇı´du homomorfismu° C mezi konecˇneˇ generovany´mi volny´mi pologrupami s na´-
sledujı´cı´mi vlastnostmi:
 Necht’A;B;C jsou libovolne´ konecˇne´ abecedy. Jestlizˇe f ;g 2 C , kde f : A+ !B+,
g : B+ !C+, pak g  f 2 C , kde g  f : A+ !C+.
 Pro libovolnou konecˇnou abecedu A platı´, zˇe idA+ : A+ !A+ 2 C .
Pozna´mka. Pro cˇtena´rˇe znale´ problematiky teorie kategoriı´ je vhodne´ poznamenat, zˇe trˇı´da
C je trˇı´dou morfismu° v kategorii, jejı´zˇ objekty jsou vsˇechny konecˇneˇ generovane´ volne´
pologrupy. Howard Straubing ve sve´ pra´ci [21] mı´rneˇ neprˇesneˇ hovorˇı´ o trˇı´deˇ C jako
o kategorii. I my v nasˇı´ pra´ci pouzˇijeme tuto terminologii a nada´le tedy budeme trˇı´du C
oznacˇovat jako kategorii C .
Prˇı´klad 2.1. Vnasˇı´ pra´ci se budeme nejvı´ce zaby´vat dveˇma kategoriemi a to Call a Clit , kde
Call je kategorie vsˇech homomorfismu° mezi konecˇneˇ generovany´mi volny´mi pologrupami,
a Clit je kategorie tzv. litera´lnı´ch homomorfismu°, tj. vsˇech homomorfismu° f : A+ !B+
takovy´ch, zˇe f (A)  B, neboli takovy´ch, zˇe pro libovolne´ a 2 A platı´ f (a) 2 B. Dalsˇı´m
prˇı´kladem kategorie C je kategorie Clm vsˇech de´lku na´sobı´cı´ch homomorfismu°, tj. homomorfismu°
f : A+ !B+ takovy´ch, zˇe existuje k 2 N tak, zˇe f (A)  Bk. Dalsˇı´mi prˇı´klady
– 11 –
Kapitola 2. C -variety jazyku° 12
kategoriı´ homomorfismu° jsou Cin j a Csur, kde Cin j je kategorie vsˇech injektivnı´ch homomorfismu°
mezi konecˇneˇ generovany´mi volny´mi pologrupami a Csur je kategorie vsˇech
surjektivnı´ch homomorfismu° mezi konecˇneˇ generovany´mi volny´mi pologrupami.
Protozˇe slovnı´ spojenı´ kategorie homomorfismu° C mezi vsˇemi konecˇneˇ generovany´mi
volny´mi pologrupami je pomeˇrneˇ dlouhe´, budeme tuto kategorii zkra´ceneˇ nazy´vat pouze
kategorie homomorfismu° C .
Definice 2.2. Necht’C je kategorie homomorfismu° a S je trˇı´da vsˇech surjektivnı´ch homomorfismu°
s : A+ !S, kde A je konecˇna´ abeceda a S konecˇna´ pologrupa. Trˇı´da V  S se
nazy´va´ C -pseudovarieta homomorfismu°, jestlizˇe platı´ na´sledujı´cı´ podmı´nky:
 Jestlizˇe s : A+!S je ve V a h : S!P je surjektivnı´ homomorfismus pologrup, pak
h s : A+ !P je ve V.
 Jestlizˇe s : B+ !S je ve V a f : A+ !B+ je v C , pak s  f : A+ !Im(s  f ) je ve
V.
 Jestlizˇe s : A+ !S a t : A+ !P jsou ve V, pak i s t : A+ !Im(s t)  SP
je ve V.
Pozna´mka. Ma´me-li neˇjakou trˇı´du M surjektivnı´ch homomorfismu° s : A+ ! S, kde A
je konecˇna´ abeceda a S konecˇna´ pologrupa, pak symbolem V(M) oznacˇı´me nejmensˇı´
C -pseudovarietu obsahujı´cı´ M a rˇekneme, zˇe V(M) je generovana´ trˇı´dou M. Nejmensˇı´
C -pseudovarieta obsahujı´cı´ trˇı´du M je pru°nikem vsˇech C -pseudovariet obsahujı´cı´ch M.
Definice 2.3. Necht’C je kategorie homomorfismu°. C -varieta jazyku° je prˇirˇazenı´ V , ktere´
kazˇde´ konecˇne´ abecedeˇ A prˇirˇadı´ mnozˇinu V (A) regula´rnı´ch jazyku° splnˇujı´cı´ na´sledujı´cı´
podmı´nky:
 V (A) je uzavrˇena´ na booleovske´ operace.
 Jestlizˇe L 2 V (A) a a 2 A, pak kvocienty a􀀀1L;La􀀀1 jsou ve V (A).
 Jestlizˇe L 2 V (A) a f : B+ !A+ je v C , pak f 􀀀1(L) 2 V (B).
Na´sleduje veˇta, jezˇ je zobecneˇnı´m klasicke´ Eilenbergovy korespondence zavedene´
v [5]. Zobecneˇna´ Eilenbergova korespondence rˇı´ka´, zˇe trˇı´dy regula´rnı´ch jazyku°, ktere´ lze
popsat pomocı´ C -pseudovariet homomorfismu°, jsou pra´veˇ C -variety jazyku°. Du°kaz te´to
veˇty lze nale´zt v [21].
Veˇta 2.4. Necht’C je kategorie homomorfismu°. Pro C -pseudovarietu homomorfismu° V
symbolem a(V) oznacˇme C -varietu regula´rnı´ch jazyku° danou
a(V)(A) = fL  A+ j mL 2 Vg
pro libovolnou abecedu A. Da´le necht’ V je C -varieta regula´rnı´ch jazyku°. Symbolem
b(V ) oznacˇme C -pseudovarietu homomorfismu° generovanou syntakticky´mi homomorfismy
mL : A+ !S, kde A je abeceda, L 2 V (A) regula´rnı´ jazyk a S konecˇna´ pologrupa.
Pak a a b jsou vza´jemneˇ inverznı´ izomorfismy C -pseudovariet homomorfismu° a C -variet
regula´rnı´ch jazyku°.
Kapitola 2. C -variety jazyku° 13
2.2 Identity
Za´kladnı´m poznatkem univerza´lnı´ algebry je Birkhoffova veˇta z [2], ktera´ rˇı´ka´, zˇe variety
algeber jsou pra´veˇ ty trˇı´dy, ktere´ lze zadat mnozˇinou identit. Modifikacı´ pro konecˇne´ algebry
se zaby´valo vı´ce autoru° a hlavnı´ vy´sledek podal Jan Reiterman v [19], ktery´ rˇı´ka´, zˇe
pseudovariety algeber lze popsat pomocı´ pseudoidentit. Algebraicka´ teorie regula´rnı´ch jazyku°
pak vedla ke snaze podat podobnou veˇtu i pro C -pseudovariety homomorfismu° mezi
konecˇneˇ generovany´mi volny´mi pologrupami a konecˇny´mi pologrupami. Tento vy´sledek
podal Michal Kunc v [11]. Dalsˇı´m autorem, jezˇ se zaby´val variantou univerza´lnı´ algebry
pro C -variety a C -pseudovariety homomorfismu°, je Libor Pola´k, a to v [18]. V neˇktery´ch
prˇı´padech, kdy jsou odpovı´dajı´cı´ pseudovariety pologrup/homomorfismu° loka´lneˇ konecˇne´,
cozˇ lze ekvivalentneˇ vyja´drˇit tak, zˇe V (A) je konecˇna´ pro libovolnou abecedu A, stacˇı´ k popisu
C -pseudovariet homomorfismu° identity namı´sto pseudoidentit. To bude na´sˇ prˇı´pad
a budeme proto definovat pouze splnˇovanı´ identit.
V dalsˇı´m textu budeme symbolem X oznacˇovat spocˇetnou mnozˇinu promeˇnny´ch, tj.
X =fx1;x2; : : :g, a pro libovolne´ n 2Noznacˇı´me Xn =fx1; : : : ;xng. Nada´le take´ prˇedpokla´-
dejme, zˇe pro libovolna´ k  l obsahuje kategorie C vsˇechny homomorfismy i : X+
k !X+
l
takove´, zˇe pro libovolne´ i 2 f1; : : : ;kg platı´ i(xi)=xi. Tyto homomorfismy zrˇejmeˇ prˇedstavujı
´ inkluze X+
k  X+
l . Oznacˇme X+ =
S¥ n=1X+
n . Zrˇejmeˇ pak pro libovolne´ s 2 X+ platı´,
zˇe existuje n 2 N tak, zˇe s 2 X+
n , jiny´mi slovy prvek s obsahuje nejvy´sˇe n promeˇnny´ch
x1; : : : ;xn.
Definice 2.5. Identitou nad X nazveme libovolnou dvojici (s; t) prvku° s; t 2 X+, budeme
zapisovat s l t. Rˇ ekneme, zˇe pro homomorfismus s : A+ ! S 2 S platı´, zˇe C -splnˇuje
identitu s l t, nebo zˇe identita s l t je C -splneˇna homomorfismem s : A+ !S, jestlizˇe
pro libovolny´ homomorfismus f : X+
n ! A+ 2 C , kde n 2 N je minima´lnı´ takove´, zˇe
s; t 2 X+
n , platı´
s( f (s)) = s( f (t)):
Budeme zapisovat s j=C s l t.
Pozna´mka. Dı´ky tomu, zˇe kategorie C obsahuje homomorfismy i : X+
k ! X+
l popsane´
vy´sˇe, platı´ vlastnost s( f (s)) = s( f (t)) pro vsˇechna f : X+
m ! A+ 2 C , kde m 2 N je
libovolne´ takove´, zˇe s; t 2 X+
m .
Jestlizˇe V  S je C -pseudovarieta homomorfismu°, pak symbolem IdC (V) oznacˇı´me
mnozˇinu vsˇech identit, jezˇ jsou C -splneˇny homomorfismy z V, tj.
IdC (V) = fp 2 X+X+ j 8s 2 V : s j=C pg:
Jestlizˇe P  X+ X+ je mnozˇina identit nad X, pak oznacˇı´me ModCP trˇı´du vsˇech
homomorfismu° s 2 S, jezˇ C -splnˇujı´ identity z P, tedy
ModCP = fs 2 S j 8p 2 P : s j=C pg:
Tato trˇı´da ModCP je C -pseudovarieta homomorfismu°.
Kapitola 2. C -variety jazyku° 14
Definice 2.6. Necht’P je mnozˇina identit nad X a ModCP je C -pseudovarieta homomorfismu°,
jezˇ C -splnˇujı´ identity z P. Rˇ ekneme, zˇe identita s l t je du°sledkem identit z P,
jestlizˇe pro libovolny´ homomorfismus s 2 ModCP platı´, zˇe C -splnˇuje identitu s l t, tj.
s j=C s l t. Mnozˇinu vsˇech du°sledku° P oznacˇı´me D(P).
Uvedeme si nynı´ variantu veˇty o u´plnosti ekvaciona´lnı´ logiky pro C -variety homomorfismu°.
Pu°vodnı´ zneˇnı´ pro variety algeber zformuloval a doka´zal Garrett Birkhoff v [2],
nale´zt lze take´ v [3]. Du°kaz veˇty o u´plnosti ekvaciona´lnı´ logiky pro C -variety homomorfismu°
by se provedl podobneˇ jako pro variety algeber na za´kladeˇ pra´ce [18].
Veˇta 2.7 (U´ plnost ekvaciona´lnı´ logiky). Necht’C je kategorie homomorfismu°, P mnozˇina
identit nad X a s l t identita nad X. Pak platı´, zˇe s l t je du°sledkem P pra´veˇ tehdy,
kdyzˇ existuje m 2 N a po dvou ru°zna´ t0; : : : ; tk 2 X+ takova´, zˇe s = t0; t = tk a pro kazˇde´
i 2 f0; : : : ;k 􀀀1g existujı´ pi;qi 2 X;ui;vi 2 X+
m a homomorfismus fi : X+
m ! X+
m 2 C
takove´, zˇe ti = pi fi(ui)qi; ti+1 = pi fi(vi)qi a ui l vi 2 P.
Definice 2.8. Posloupnost identit s = t0 l t1; t1 l t2; : : : ; tk􀀀1 l tk = t z prˇedchozı´ veˇty
nazveme du°kazem identity s l t z mnozˇiny identit P.
Definice 2.9. Necht’V je C -pseudovarieta homomorfismu°, IdC (V) mnozˇina vsˇech identit
nad X, jezˇ jsou C -splneˇny homomorfismy z V. Mnozˇinu identit PIdC (V) nazveme ba´zı´
identit, jestlizˇe platı´ D(P) = IdC (V). Jiny´mi slovy kazˇda´ identita z IdC (V) je du°sledkem
mnozˇiny identit P. V prˇı´padeˇ, zˇe je mnozˇina P konecˇna´, rˇekneme, zˇe V ma´ konecˇnou ba´zi
identit.



V teorii forma´lnı´ch jazyku° se vyuzˇı´vajı´ dva prˇı´stupy k jazyku°m. Prvnı´ z nich definuje jazyky
jako podmnozˇiny A+ a druhy´ jako podmnozˇiny A. My v te´to pra´ci budeme pracovat
s jazyky jako podmnozˇinami A+ a tedy s pologrupou A+. Vesˇkere´ definice a veˇty by sˇly
mı´rnou modifikacı´ upravit i pro prˇı´pad A.
Jazyk L nad abecedou A je libovolna´ podmnozˇina A+, tj. libovolna´ mnozˇina nepra´zdny
´ch slov nad abecedou A.
Meˇjme jazyky L;K  A+. Vzhledem k tomu, zˇe L i K jsou mnozˇiny, mu°zˇeme na neˇ
aplikovat obvykle´ operace sjednocenı´, pru°nik a komplement. Navı´c si definujeme operace
zrˇeteˇzenı´, iterace a pozitivnı´ iterace.
Zrˇeteˇzenı´: L K = fuv j u 2 L a v 2 Kg
Iterace: L = fu1 : : :un j n  0 a u1; : : : ;un 2 Lg
Pozitivnı´ iterace: L+ = fu1 : : :un j n > 0 a u1; : : : ;un 2 Lg
Mimo operace uvedene´ v prˇedchozı´m odstavci, mu°zˇeme pracovat take´ s pravy´mi
a levy´mi kvocienty jazyka.
Definice 1.16. Necht’A je abeceda, L  A+ jazyk a a 2 A pı´smeno. Pro jazyk L definujeme
levy´ a pravy´ kvocient podle a prˇedpisy
a􀀀1L = fu 2 A+ j au 2 Lg;
La􀀀1 = fu 2 A+ j ua 2 Lg:
Uvedli jsme si obvykle´ operace s jazyky a nynı´ mu°zˇeme zadefinovat trˇı´du regula´rnı´ch
jazyku°.
Definice 1.17. Necht’A je abeceda. Trˇı´du regula´rnı´ch jazyku° nad abecedou A definujeme
induktivneˇ takto:
1. Mnozˇiny /0 a fag pro kazˇde´ a 2 A jsou regula´rnı´ jazyky nad abecedou A.
2. Jsou-li L;K  A+ regula´rnı´ jazyky, pak jsou te´zˇ L[K;L K;L+ regula´rnı´mi jazyky
nad abecedou A.
3. Kazˇdy´ regula´rnı´ jazyk nad abecedou A vznikne po konecˇne´m pocˇtu aplikacı´ kroku°
1. a 2.
1.4 Konecˇne´ automaty
Tradicˇnı´m na´strojem v teoreticke´ informatice, jak popsat neˇjaky´ regula´rnı´ jazyk, je zadat
konecˇny´ automat, ktery´ dany´ jazyk rozpozna´va´.
Definice 1.18. Konecˇny´ deterministicky´ automat A je peˇtice (Q;A;d;q0;F), kde
Kapitola 1. Algebraicka´ teorie regula´rnı´ch jazyku° 6
 Q je nepra´zdna´ konecˇna´ mnozˇina stavu°,
 A je konecˇna´ abeceda,
 d : QA!Q je prˇechodova´ funkce,
 q0 2 Q je pocˇa´tecˇnı´ (inicia´lnı´) stav,
 F  Q je mnozˇina koncovy´ch stavu°.
Pozna´mka. Protozˇe se v tomto textu nebudeme zaby´vat zˇa´dny´mi jiny´mi automaty nezˇ
deterministicky´mi, budeme nada´le pouzˇı´vat zkra´cene´ oznacˇenı´ konecˇny´ automat.
Pro definici jazyka prˇijı´mane´ho dany´m automatem je trˇeba nejdrˇı´ve zave´st tzv. rozsˇı´rˇenou
pˇrechodovou funkci dˆ : QA+!Q. Definujeme ji induktivneˇ vzhledemk de´lce slova
z A+:
 dˆ(q;a) = d(q;a) pro q 2 Q;a 2 A,
 dˆ(q;ua) = d(dˆ(q;u);a) pro q 2 Q;u 2 A+;a 2 A.
Za´pis dˆ(q;u) = p znacˇ´ı, zˇe je-li automat ve stavu q a pˇrecˇte slovo u, pak se pˇresune do
stavu p. Indukcı´ lze snadno doka´zat, zˇe pro libovolna´ slova u;v 2 A+ a stav q 2 Q platı´
dˆ(q;uv) = dˆ(dˆ(q;u);v):
Slovo u 2 A+ je rozpozna´vane´ automatemA, jestlizˇe se automat z pocˇa´tecˇnı´ho stavu q0,
po prˇecˇtenı´ slova u, prˇesune do neˇjake´ho koncove´ho stavu. Jazyk L(A)A+ rozpozna´vany´
automatem A je mnozˇina vsˇech slov u 2 A+ rozpozna´vany´ch automatem A, neboli
L(A) = fu 2 A+ j dˆ(q0;u) 2 Fg:
Konecˇne´ automaty se dajı´ na´zorneˇ zakreslit pomocı´ prˇechodove´ho grafu. Uvedeme si
nynı´ prˇı´klad konecˇne´ho automatu a jazyka, ktery´ je tı´mto automatem rozpozna´vany´.
Prˇı´klad 1.19. Meˇjme konecˇny´ automat A = (fq0;q1g;fa;b;cg;d;q0;fq1g), kde
d(q0;a) = q0; d(q0;b) = q0; d(q0;c) = q1;
d(q1;a) = q1; d(q1;b) = q1; d(q1;c) = q1:
Prˇechodovy´ graf automatu A je zna´zorneˇn na obra´zku 1.1 a jazyk rozpozna´vany´ tı´mto
automatem A je L(A) = fa;bg  fcg A.
Na´sledujı´cı´ veˇta na´m rˇı´ka´, zˇe regula´rnı´ jazyky jsou pra´veˇ jazyky rozpozna´vane´ konec
ˇny´mi automaty. Zformuloval ji Stephen Cole Kleene a jejı´ du°kaz lze nale´zt naprˇı´klad
v [4].
Veˇta 1.20. Libovolny´ jazyk LA+ je regula´rnı´ pra´veˇ tehdy, kdyzˇ existuje konecˇny´ automat
A takovy´, zˇe L = L(A).
V na´sledujı´cı´ definici si zavedeme pojem minima´lnı´ho automatu.
Kapitola 1. Algebraicka´ teorie regula´rnı´ch jazyku° 7
Obra´zek 1.1: konecˇny´ automat z prˇı´kladu 1.19
Definice 1.21. Konecˇny´ automatAse nazy´va´ minima´lnı´, jestlizˇe neexistuje zˇa´dny´ konecˇny´
automat s me´neˇ stavy nezˇ ma´ A rozpozna´vajı´cı´ jazyk L(A).
Pozna´mka. Automat A z prˇı´kladu 1.19 je zrˇejmeˇ minima´lnı´, nebot’ma´ pouze dva stavy
a to inicia´lnı´ a koncovy´. Automat nemu°zˇe mı´t me´neˇ stavu°, nebot’automat s pouze jednı´m
stavem rozpozna´va´ bud’A+ nebo /0.
Veˇta 1.22. Pro kazˇdy´ regula´rnı´ jazyk L  A+ existuje, azˇ na izomorfismus, pra´veˇ jeden
minima´lnı´ automat.
Du°kaz prˇedcha´zejı´cı´ veˇty lze nale´zt naprˇı´klad v [4]. Tento du°kaz je vlastneˇ algoritmem,
jak pro libovolny´ automat A a jazyk L(A) rozpozna´vany´ tı´mto automatem sestrojit
minima´lnı´ automat.
1.5 Algebraicke´ rozpozna´va´nı´ jazyku°
Nynı´ si uvedeme, jak z konecˇne´ho automatu zı´skat konecˇnou pologrupu, a da´le take´ jaky´m
zpu°sobem jsme schopni zada´vat jazyky pomocı´ pologrup.
Meˇjme konecˇny´ automat A = (Q;A;d;q0;F). Kazˇde´ slovo u 2 A+ urcˇuje transformaci
du : Q!Q pˇredpisem du(q) = dˆ(q;u) pro q 2 Q. Transformacˇn´ı pologrupou automatu A
nazveme pologrupu (fdu j u 2 A+g; ), kde operace  je definova´na:
(du  dv)(q) = duv(q) = dv(du(q)); neboli (du  dv)(q) = dˆ(q;uv):
Transformacˇnı´ pologrupu automatu A znacˇı´me S(A). Tato pologrupa je zrˇejmeˇ konecˇna´,
nebot’pro konecˇnou mnozˇinu Q existuje pouze konecˇneˇ mnoho transformacı´ du : Q!Q.
Slovo u 2 A+ je rozpozna´va´no automatem A pra´veˇ tehdy, kdyzˇ du(q0) 2 F. Jinak
rˇecˇeno, jazyk rozpozna´vany´ automatem A je pra´veˇ
L(A) = fu 2 A+ j du(q0) 2 Fg:
Zaved’me homomorfismus j : A+!S(A) prˇedpisem j(u) = du pro libovolne´ u 2 A+.
Pak platı´ L(A) = j􀀀1(X), kde X = fdu j du(q0) 2 Fg.
Prˇedchozı´ definice transformacˇnı´ pologrupy a homomorfismu j na´s prˇiva´dı´ k algebraicke
´mu popisu regula´rnı´ch jazyku°, kdy vyuzˇı´va´me pologrupy a homomorfismy pologrup.
Uvedene´ definice jsou pro obecnou pologrupu S. Pozdeˇji uvedeme veˇtu, jezˇ na´m rˇı´ka´, zˇe
regula´rnı´ jazyky jsou pra´veˇ jazyky rozpozna´vane´ konecˇny´mi pologrupami.
Kapitola 1. Algebraicka´ teorie regula´rnı´ch jazyku° 8
Definice 1.23. Necht’A je abeceda, S pologrupa a j : A+ !S homomorfismus pologrup.
Rˇ
ekneme, zˇe jazyk L  A+ je rozpozna´vany´ homomorfismem j, jestlizˇe existuje mnozˇina
X  S takova´, zˇe L = j􀀀1(X).
Definice 1.24. Necht’A je abeceda a S pologrupa.Rˇ ekneme, zˇe jazyk L  A+ je rozpozna´-
vany´ pologrupou S, jestlizˇe existuje homomorfismus j : A+ !S a mnozˇina X  S takova´,
zˇe L = j􀀀1(X).
Mu°zˇeme tedy nynı´ uve´st lemma, ktere´ na´m da´va´ alternativnı´ popis regula´rnı´ch jazyku°
pomocı´ transformacˇnı´ch pologrup. Jeho du°kaz si nebudeme uva´deˇt, ale pouze zmı´nı´me,
zˇe by se pouzˇilo homomorfismu j : A+ ! S(A), kde j(u) = du pro libovolne´ u 2 A+,
a mnozˇiny X = fdu j du(q0) 2 Fg.
Lemma 1.25. Jestlizˇe konecˇny´ automat A rozpozna´va´ jazyk L, pak i transformacˇnı´ pologrupa
S(A) rozpozna´va´ jazyk L.
Prˇedchozı´ konstrukci, kdy jsme z konecˇne´ho automatu vytva´rˇeli konecˇnou pologrupu,
mu°zˇeme obra´tit, tzn. budeme-li mı´t konecˇnou pologrupu, pak jsme k nı´ schopni zkonstruovat
konecˇny´ automat. Tı´m bychom dostali tvrzenı´, zˇe regula´rnı´ jazyky jsou pra´veˇ jazyky
rozpozna´vane´ konecˇny´mi pologrupami. Toto tvrzenı´ zformulujeme pozdeˇji spolecˇneˇ s dals
ˇı´mi mozˇnostmi charakterizace regula´rnı´ch jazyku°.
Dalsˇı´ alternativou, jak algebraicky rozpozna´vat jazyky, je pouzˇitı´ kongruencı´ na pologrupe
ˇ A+.
Definice 1.26. Necht’A je abeceda aA+A+ kongruence na pologrupeˇ A+.Rˇ ekneme,
zˇe jazyk L  A+ je rozpozna´vany´ kongruencı´ , jestlizˇe pro vsˇechna u 2 L;v 2 A+ platı´
u  v =)v 2 L:
Pozna´mka. Prˇedchozı´ definice na´mrˇı´ka´, zˇe jazyk L je rozpozna´vany´ kongruencı´, jestlizˇe
je sjednocenı´m neˇktery´ch trˇı´d rozkladu A+= .
Dosavadnı´ poznatky o regula´rnı´ch jazycı´ch mu°zˇeme shrnout do varianty Kleeneho
veˇty. Jejı´ du°kaz mu°zˇeme nale´zt naprˇı´klad v [16].
Veˇta 1.27. Necht’A je abeceda a L  A+ je jazyk. Pak na´sledujı´cı´ podmı´nky jsou ekvivalentnı
´:
 Jazyk L je regula´rnı´.
 Jazyk L je rozpozna´vany´ konecˇny´m automatem.
 Jazyk L je rozpozna´vany´ konecˇnou pologrupou.
 Jazyk L je rozpozna´vany´ kongruencı´ na pologrupeˇ A+ s konecˇny´m indexem.
Kapitola 1. Algebraicka´ teorie regula´rnı´ch jazyku° 9
1.6 Syntakticka´ pologrupa
Tak jako jsme mezi konecˇny´mi automaty meˇli jeden vy´znacˇny´, tzv. minima´lnı´, tak bychom
ra´di meˇli i neˇjakou vy´znacˇnou pologrupu. Touto pologrupou bude syntakticka´ pologrupa,
o nı´zˇ lze doka´zat, zˇe je izomorfnı´ transformacˇnı´ pologrupeˇ minima´lnı´ho automatu. Prˇed
samotnou definicı´ syntakticke´ pologrupy musı´me nejprve uve´st definici syntakticke´ kongruence.
Definice 1.28. Meˇjme abecedu A a jazyk L  A+. Na mnozˇineˇ A+ definujeme relaci
L  A+A+ na´sledovneˇ:
u L v; pra´veˇ kdyzˇ pro vsˇechna x;y 2 A platı´ xuy 2 L()xvy 2 L:
Veˇta 1.29. Relace L  A+A+ z definice 1.28 je kongruence na pologrupeˇ A+.
Du°kaz. Zrˇejmeˇ je relace L ekvivalence na pologrupeˇ A+. Da´le doka´zˇeme, zˇe platı´ charakterizace
kongruence z veˇty 1.15. Meˇjme tedy a 2 A a u;u0 2 A+, pro neˇzˇ platı´ uL u0. To
znamena´, zˇe pro libovolna´ x;y 2 A ma´me xuy 2 L()xu0y 2 L. Pak xuay 2 L, pra´veˇ kdyzˇ
xuz 2 L, kde z = ay. To je ale pra´veˇ tehdy, kdyzˇ xu0z 2 L, nebot’u L u0. To je ekvivalentnı´
tomu, zˇe xu0ay 2 L. Celkem jsme dostali xuay 2 L()xu0ay 2 L, neboli ua L u0a. Du°kaz
druhe´ podmı´nky au L au0 se provede analogicky.
Pozna´mka. Relace L se nazy´va´ syntakticka´ kongruence jazyka L.
Nynı´ jizˇ mu°zˇeme uve´st definici samotne´ syntakticke´ pologrupy a take´ definici syntakticke
´ho homomorfismu.
Definice 1.30. Meˇjme abecedu A, jazyk L  A+ a syntaktickou kongruenci L jazyka
L. Pak faktorovou pologrupu (A+= L; ) nazveme syntaktickou pologrupou jazyka L
a projekci m : A+ !A+= L nazveme syntakticky´m homomorfismem.
Pozna´mka. Syntaktickou pologrupu A+= L jazyka L budeme znacˇit S(L).
Bylo by vhodne´ mı´t neˇjaky´ efektivnı´ zpu°sob, jak syntaktickou pologrupu jiste´ho jazyka
zı´skat. K tomu na´m ale slouzˇı´ na´sledujı´cı´ veˇta, jejı´zˇ du°kaz mu°zˇeme nale´zt naprˇı´klad v [1].
Veˇta 1.31. Necht’A je abeceda a LA+ regula´rnı´ jazyk. Pak syntakticka´ pologrupa jazyka
L je izomorfnı´ transformacˇnı´ pologrupeˇ minima´lnı´ho automatu jazyka L.
S ohledem na prˇedchozı´ veˇtu dosta´va´me tvrzenı´, dı´ky ktere´mu mu°zˇeme jazyk L popsat
jeho syntaktickou pologrupou. Du°kaz tohoto tvrzenı´ mu°zˇeme nale´zt v [23].
Veˇta 1.32. Jazyk L  A+ je regula´rnı´ pra´veˇ tehdy, kdyzˇ jeho syntakticka´ pologrupa je
konecˇna´.
Nynı´ na´sleduje veˇta, ktera´ rˇı´ka´, zˇe mezi vsˇemi kongruencemi na pologrupeˇ A+ je
syntakticka´ kongruence ta nejveˇtsˇı´.
Veˇta 1.33. Necht’A je abeceda,  libovolna´ kongruence na A+, L  A+ jazyk, jenzˇ je
sjednocenı´m neˇktery´ch trˇı´d rozkladu A+= , a L syntakticka´ kongruence jazyka L. Pak
platı´   L.

\end{document}




